package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;
import lombok.extern.slf4j.Slf4j;


@Slf4j
public class Sort10_归并排序 implements IAS {

    @Override
    public void sort(int[] arr) {
        marge(arr, 0, arr.length - 1);
    }

    public void marge(int[] arr, int begin, int end) {

        if (begin < end) {
            int mid = (begin + end) / 2;
            marge(arr, begin, mid);
            marge(arr, mid + 1, end);
            margeSort(arr, begin, mid, end);
        }
    }

    public void margeSort(int[] arr, int begin, int mid, int end) {
        int len = end - begin + 1;
        if (len <= 1) {
            return;
        }

        int[] tmp = new int[len];

        // 左边的开始
        int left = begin;
        // 右边的开始
        int right = mid + 1;

        int idx = 0;
        while (left <= mid && right <= end) {
            if (arr[left] < arr[right]) {
                tmp[idx++] = arr[left++];
            } else {
                tmp[idx++] = arr[right++];
            }
        }

        while (left <= mid) {
            tmp[idx++] = arr[left++];
        }

        while (right <= end) {
            tmp[idx++] = arr[right++];
        }

        for (int i = begin; i <= end; i++) {
            arr[i] = tmp[i - begin];
        }
    }

}
